#include<stdio.h>
#include<conio.h>
#include<alloc.h>

int n;

void swap(int *x,int *y)
{
 int temp;
 temp=*x;
 *x=*y;
 *y=temp;
}

void qsort(int *x,int left,int right)
{
  int key,i,j,count;

  if(left<right)
  {
   key=x[left];
   i=left+1;
   j=right;

   do
    {
     while (key>x[i] && i<=right) i++;
     while (key<x[j] && j>left  ) j--;
     if (i<=j) swap(x+i,x+j);
    } while (i<j);
   swap(x+left,x+j);
   printf("\n");
   for(count=0;count<n;count++)
    printf("%d ",x[count]);
   qsort(x,left,j-1);
   qsort(x,j+1,right);
  }
}

void main()
{
 int *a,i;

 clrscr();
 printf("--- QUICKSORT ---\n");
 printf("No. of elements:");
 scanf("%d",&n);
 a=(int*)malloc(n*sizeof(int));

 printf("\nList Input\n");
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);

 printf("\nWorking. . .");
 qsort(a,0,n-1);
 printf("\n\nSorted List\n");
 for(i=0;i<n;i++)
  printf("%d ",a[i]);
 getch();
}

